package net.tp.algo.sort.network;

/**
 * <p>Odd Even Merge Sort.</p>
 *
 * <p>Assuming $n=2^p$. Odd even merge sort is a divide-conquer algorithm. It sorts the left and right half sequences. To merge the result, it merges the odd values, the even values, then it compare-swaps all the odd-even pairs.</p>
 *
 * <p>For example, to sort sequence 7 2 5 4 6 1 0 3:</p>
 * <pre>
 * Sort 2 halves:  2 4 5 7-0 1 3 6
 * Merge odd    :    1   4   6   7
 * Merge even   :  0   2   3   5
 * compare-swap :    1:2 3:4 5:6
 * result       :  0 1 2 3 4 5 6 7
 * </pre>
 *
 * <p><strong>Odd-Even Merge sorting network</strong></p>
 * <pre>
 *  sort halves    merge odd/even   compare
 * ──╮───╮──────── ───╮─────────── ─────────
 * ──╵───│╮───╮─── ───│╮────────── ───╮─────
 * ──╮───╵│───╵─── ───││╮────╮──── ───╵─────
 * ──╵────╵─────── ───│││╮───│╮─── ───╮─────
 * ──╮───╮──────── ───╵│││───╵│─── ───╵─────
 * ──╵───│╮───╮─── ────╵││────╵─── ───╮─────
 * ──╮───╵│───╵─── ─────╵│──────── ───╵─────
 * ──╵────╵─────── ──────╵──────── ─────────
 * </pre>
 *
 * @author Trung Phan
 * @see BitonicSort
 * @time $O(n \log ^2 n)$
 *
 */
public class OddEvenMergeSort {

    public static void sort(int[] a) {
        int n = a.length;
        if (n != (n & ~(n-1))) throw new IllegalArgumentException("n must be power of 2: " + n);

        sort(a, 0, n);
    }

    public static void sort(int[] a, int lo, int n) {
        if (n <= 1) return;
        int m = n/2;
        sort(a, lo, m);
        sort(a, lo + m, m);
        merge(a, lo, n, 1);
    }

    private static void merge(int[] a, int lo, int n, int d) {
        if (2*d < n) {
            merge(a, lo + d, n-d, d*2); // merge odd
            merge(a, lo, n, d*2); // merge even
            for (int i = lo+d; i < lo+n-d; i+= 2*d)
                compareAndSwap(a, i, i+d); // compare odd-even
        }
        else
            compareAndSwap(a, lo, lo+d);

    }

    private static void compareAndSwap(int[] a, int i, int j) {
        if (a[i] > a[j]) {
            int tmp = a[i];
            a[i] = a[j];
            a[j] = tmp;
        }
    }

}
